Search in Rotated Sorted Array
题目大意
把一个严格升序的数组进行旋转，如[0,1,2,3,4,5]旋转3位成为[3,4,5,0,1,2]。在这样的数组中找到目标数字。如果存在返回下标，不存在返回-1。
输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 6 输出: 2
输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 输出: -1
解题思路
二分搜索是针对有序数组而言，对于中间有次转折的有序数组，只是要多区分几种情况，二分搜索依然是适用的。
主要就是判断mid的左右哪边是中断的
代码
该解法的判断表达是对称的结构，有助于记忆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0; right = len(nums) - 1
while left <= right:
mid = (left + right) / 2
if target == nums[mid]:
return mid
if nums[mid] >= nums[left]: # 中点大于最左边，说明左边区间没有混乱
if target < nums[mid] and target >= nums[left]: # 此时若目标数小于中间数而且大于最左边，说明就在左边区间
right = mid - 1
else: # 不然就在右边区间
left = mid + 1
else: # 中点小于最右边，说明右边区间没有混乱
if target > nums[mid] and target <= nums[right]: # 此时若目标数大于中间数而且小于最右边，说明就在右边区间
left = mid + 1
else: # 不然就在左边区间
right = mid - 1
return -1 # 找不到
|
Search in Rotated Sorted Array II
题目大意
把一个有重复的排序数组进行旋转，如[0,1,1,1,2,3,4,5]旋转3位成为[3,4,5,0,1,1,1,2]。在这样的数组中判断目标数字是否存在。
解题思路
和上题其实唯一的区别在于如果重复的数字中间进行了旋转，所以只要加入
1
2
3
| if nums[left] == nums[mid] == nums[right]:
left += 1
right -= 1
|
其他相同。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
left = 0; right = len(nums)-1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
if nums[left] == nums[mid] == nums[right]: # 所有指针都一个数字，说明旋转时有的在左边有的在右边，需要往中间看
left += 1
right -= 1
elif nums[mid] >= nums[left]: # 中点大于最左边，说明左边区间没有混乱
if target < nums[mid] and target >= nums[left]: # 此时若目标数小于中间数而且大于最左边，说明就在左边区间
right = mid - 1
else: # 不然就在右边区间
left = mid + 1
else: # 中点小于最右边，说明右边区间没有混乱
if target > nums[mid] and target <= nums[right]: # 此时若目标数大于中间数而且小于最右边，说明就在右边区间
left = mid + 1
else: # 不然就在左边区间
right = mid - 1
return False
|
总结